package sort;

public class ShellSort {
    public static void main(String[] args) {
        //int[] arr = {3, 1, 5, 9, 7, 8, 6, -10, 20, 14, -104};
        long startTime = System.currentTimeMillis();
        int[] arr = new int[80000];
        initArr(arr);
        shellSort(arr);
        //myShellSort(arr);
        //System.out.print(Arrays.toString(arr));
        long endTime = System.currentTimeMillis();
        System.out.println("程序运行时间：" + (endTime - startTime) + "ms");
        //System.out.println(Arrays.toString(arr));
    }

    static void initArr(int[] arr) {

        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 800000);
        }
    }

    static void shellSortSwap(int[] arr) {     //交换版的希尔排序，频繁交换，效率低
        int temp = 0;
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                for (int j = i - gap; j >= 0; j -= gap) {
                    if (arr[j] > arr[j + gap]) {
                        temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }
        }
    }

    public static void shellSort(int[] arr) {                   //移位版的希尔排序,可以根据插入排序修改得到，
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {     // 无非添加一个外层递减至1的增量序列循环，内层把插入递增改为gap
            for (int i = gap; i < arr.length; i++) {
                int value = arr[i];
                int p = i;
                while (p - gap >= 0 && arr[p - gap] > value) {
                    arr[p] = arr[p - gap];
                    p = p - gap;
                }
                arr[p] = value;
            }
        }
    }

    public static void myShellSort(int[] arr) { //根据你的插入排序修改的希尔排序
        for (int gap = arr.length; gap > 0; gap /= 2) {
            int temp = 0;
            int insertIndex = 0;
            for (int i = gap; i < arr.length; i++) {
                int j;
                for (j = i - gap; j >= 0; j -= gap) {  //insertIndex记录插入点下标，temp暂存待插入数据
                    if (arr[i] > arr[j]) {
                        temp = arr[i];
                        insertIndex = j + gap;
                        break;
                    }
                }
                if (j < 0) {        //如果是第一个位置,要特殊处理,这也是你的这段代码的弊端
                    temp = arr[i];
                    insertIndex = j + gap;
                }
                for (int k = i; k > insertIndex; k -= gap) {    // 如 1 3 5 2 ,待排序数据2与插入点3的位置差值移位，空出数值3的位置
                    arr[k] = arr[k - gap];
                }
                arr[insertIndex] = temp;
            }
        }
    }
}
